package stack;

import java.util.Stack;

public class ReversePolishCalculator {
    public static void main(String[] args) {
        String expr = "1.3+((2+3.5)*4.5)-5";
        Calculator c = new Calculator(expr);
        System.out.println(c.calculate());
    }
}

class Calculator {

    private Stack<Double> stack;
    public String expr;

    Calculator(String expr) {
        this.expr = expr;
        stack = new Stack<Double>();
    }

    public double calculate() {
        // 先转换为逆波兰表达式
        String[] reversePolishExpr = toReversePolish(expr);
        // 再计算结果
        return calculateReversePolish(reversePolishExpr);
    }

    // 中缀表达式转为后缀表达式
    private String[] toReversePolish(String expr) {
        Stack<String> numStack = new Stack<String>();
        Stack<String> operStack = new Stack<String>();
        // 扫描中缀表达式
        int i = 0;
        char ch = ' ';
        String number = "";
        while (i < expr.length()) {
            ch = expr.substring(i, i + 1).charAt(0);
            if (isNumber(ch)) {
                number += ch;
                if (i != expr.length() - 1) {
                    char next = expr.substring(i + 1, i + 2).charAt(0);
                    if (isOper(next) || next == '(' || next == ')') {
                        numStack.push(number);
                        number = "";
                    }
                } else {
                    numStack.push(number);
                }
            } else if (isOper(ch)) {
                while (true) {
                    if (operStack.empty() || operStack.peek() == "("
                            || getPriority(ch) > getPriority(operStack.peek().charAt(0))) {
                        operStack.push(Character.toString(ch));
                        break;
                    } else {
                        numStack.push(operStack.pop());
                    }
                }
            } else if (ch == '(') {
                operStack.push(Character.toString(ch));
            } else if (ch == ')') {
                while (true) {
                    String oper = operStack.pop();
                    if (!oper.equals("(")) {
                        numStack.push(oper);
                    } else {
                        break;
                    }
                }
            } else {
                System.out.println("!!!warning!!!");
            }
            i++;
        }
        // 将剩余运算符压入numStack
        while (!operStack.empty()) {
            numStack.push(operStack.pop());
        }
        // 逆序输出
        String[] temp = new String[numStack.size()];
        for (int j = numStack.size() - 1; j >= 0; j--) {
            temp[j] = numStack.pop();
        }
        return temp;
    }

    // 计算后缀表达式
    private double calculateReversePolish(String[] rpn) {
        for (String i : rpn) {
            if (isNumber(i)) {
                stack.push(Double.parseDouble(i));
            } else if (isOper(i.charAt(0))) {
                double num1 = stack.pop();
                double num2 = stack.pop();
                stack.push(cal(num1, num2, i.charAt(0)));
            } else {
                System.out.println("!!!warning!!!");
            }
        }
        return stack.pop();
    }

    // 判断是否为运算符
    private boolean isOper(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    // 判断是否为数字
    private boolean isNumber(String i) {
        if (i.length() >= 2) {
            return true;
        }
        return isNumber(i.charAt(0));
    }

    private boolean isNumber(char ch) {
        return (ch >= '0' && ch <= '9') || ch == '.';
    }

    // 获取运算符优先级
    private int getPriority(char ch) {
        if (ch == '*' || ch == '/') {
            return 1;
        } else if (ch == '+' || ch == '-') {
            return 0;
        } else {
            return -1;
        }
    }

    // 运算
    private double cal(double num1, double num2, char oper) {
        switch (oper) {
            case '+':
                return num1 + num2;
            case '-':
                return num2 - num1;
            case '*':
                return num1 * num2;
            case '/':
                return num2 / num1;
            default:
                return 0;
        }
    }
}
